#include "BinaryTree.h"


    struct TreeNode
    {
        TreeNode(const int &element):data(element)
        {
            left = right = nullptr;
        }
        int data;//数据域
        TreeNode *left;
        TreeNode *right;
    };

TreeNode *root = nullptr;

const int SIZE = 100;
TreeNode *nodes[SIZE] = {nullptr};

void SelectTwoMin(int size,int &min1,int &min2)
{
    min1 = min2 = -1;
    for(int i = 0;i < size;i++)
    {
        if(nodes[i])
        {
            if(min1 == -1 || nodes[i]->data < nodes[min1]->data)
            {
                min2 = min1;
                min1 = i;
            }
            else if(min2 == -1 || nodes[i]->data < nodes[min2]->data)
            {
                min2 = i;
            }
        }
    }
}

void BuildHuffmanTree(int *a,int size)
{
    for(int i = 0;i < size;i++)
    {
        nodes[i] = new TreeNode(a[i]);//把数组变成树的结点
    }
    for(int i = 0;i < size - 1;i++)
    {
        int min1,min2;//最小的两个结点
        SelectTwoMin(size,min1,min2);
        TreeNode *newnode = new TreeNode(nodes[min1]->data + nodes[min2]->data);
        newnode->left = nodes[min1];
        newnode->right = nodes[min2];

        nodes[min1] = newnode;
        nodes[min2] = nullptr;
    }

    for(int i = 0;i < size;i++)
        if(nodes[i])
        {
            root = nodes[i];
            break;
        }
}

void PrevTravel(TreeNode *node)
{
    if(node == nullptr)
        return;
    std::cout<<node->data<<" ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void MidTravel(TreeNode *node)
{
     if(node == nullptr)
        return;
    
    MidTravel(node->left);
    std::cout<<node->data<<" ";
    MidTravel(node->right);
}

int main()
{
    BinaryTree t;
    int a[] = {5,9,12,13,16,45};
    BuildHuffmanTree(a,6);
    PrevTravel(root);
    std::cout<<std::endl;
    MidTravel(root);
    std::cout<<std::endl;

    // for(int i = 0;i < 6;i++)
    //     t.Insert(a[i]);
    // t.Remove(4);
    // t.show();
    // t.Remove(6);
    // t.show();
    //std::cout<<(t.Find(2) ? "zhaodaole" : "meizhaodao")<<std::endl;
    // int *p = t.Find(4);
    // if(p)
    //     std::cout<<"找到了："<<*p<<std::endl;
    // else
    //     std::cout<<"没找到"<<std::endl;
    return 0;
}